import treeUnit from '../unit/TreeUnit.js'

/**
 * 暂未完成
 */
function TreeCode() {

    /**
     * color false 为黑 true 为红
     * blackLevel 兄黑父黑情况下控制递归向上时可以进入平衡入口
     * @param {number} value 
     */
    let TreeNode = function (value) {
        this.key = value
        this.color = true
        this.parent = null
        this.left = null
        this.right = null
    }
    const Nil = new TreeNode(null)
    Nil.color = false
    var root = Nil
    this.createTree = function () {
        // this.insert(4)
        // this.insert(1)
        // this.insert(7)
        // this.insert(3)
        // this.insert(13)
        // this.insert(5)
        // this.insert(10)
        // this.insert(14)
        // this.insert(11)
        // this.insert(6)
        // this.insert(15)
        // this.insert(8)
        // this.insert(9)
        // this.insert(12)
        // this.insert(2)
        // this.insert(16)

        this.insert(1)
        this.insert(2)
        this.insert(3)
        this.insert(4)
        this.insert(5)
        this.insert(6)
        this.insert(7)
        this.insert(8)
        this.insert(9)
        this.insert(10)
        this.insert(11)
        this.insert(12)
        this.insert(13)
        this.insert(14)
        this.insert(15)
        this.insert(16)
        return root
    }

    this.createTreeArray = () => {
        //前序遍历
        function NLR(biTree, index) {
            if (biTree === Nil) return;
            treeArray[index] = biTree.key + (biTree.color ? 'R' : 'B')
            NLR(biTree.left, 2 * index + 1);
            NLR(biTree.right, 2 * index + 2);
        }
        let treeArray = []
        NLR(root, 0)
        return treeArray
    }

    function getAddNode(key) {
        let node = new TreeNode(key)
        node.left = Nil
        node.right = Nil
        node.parent = Nil
        return node
    }
    /**
     * 插入
     * @param {number} key 结点的键值
     */
    this.insert = function (key) {
        console.log('----------------------插入节点:' + key)
        // let addNode = new TreeNode(key)
        let addNode = getAddNode(key)
        let node = root
        let addNodeParent
        while (node !== Nil) {
            addNodeParent = node
            if (key < node.key) {
                node = node.left
            } else {
                node = node.right
            }
        }
        if (root === Nil) {
            node = addNode
            root = node
        } else if (addNode.key < addNodeParent.key) {
            addNodeParent.left = addNode
            addNode.parent = addNodeParent
        } else {
            addNodeParent.right = addNode
            addNode.parent = addNodeParent
        }
        root.color = false
        // treeUnit.printTree(this.createTreeArray())
        insetFixUp(addNode)
        // treeUnit.printTree(this.createTreeArray())
    }

    /**
     * 性质4. 每个红色结点的两个子结点都是黑色。
     *  性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
     */
    function insetFixUp(node) {
        console.log('节点' + node.key + ',insetFixUp:' + isRed(node.parent))
        while (isRed(node.parent)) {
            if (node.parent === node.parent.parent.left) {
                console.log('insetFixUp left')
                let uncle = node.parent.parent.right
                if (isRed(uncle)) {
                    node.parent.color = false
                    uncle.color = false
                    uncle.parent.color = true
                    node = node.parent.parent
                    continue
                } else if (node === node.parent.right) {
                    node = node.parent
                    leftRotate(node)
                }
                node.parent.color = false
                node.parent.parent.color = true
                rightRotate(node.parent.parent)
            } else {
                console.log('insetFixUp right')
                let uncle = node.parent.parent.left
                if (isRed(uncle)) {
                    node.parent.color = false
                    uncle.color = false
                    uncle.parent.color = true
                    node = node.parent.parent
                    continue
                } else if (node === node.parent.left) {
                    node = node.parent
                    rightRotate(node)
                }
                node.parent.color = false
                node.parent.parent.color = true
                leftRotate(node.parent.parent)
            }
        }
    }
    /**
     * 翻转父子结点颜色
     * |--B(node)--|
     * R           R
     * @param {*} node 
     */
    function flipColor(node) {
        node.color = true
        node.left.color = false
        node.right.color = false
    }

    /**
     * 替换父子结点颜色
     * @param {*} node 
     */
    function exchangeColor(node) {
        let color = node.color
        node.color = node.parent.color
        node.parent.color = color
    }

    function isRed(node) {
        if (node === Nil) {
            return false
        }
        return node.color
    }

    /**
     * 
     * |-----xR-----|
     *          |--yR--|
     *          t1    zR
     * @param {object} x 平衡因子>1,待旋转的节点
     */
    function leftRotate(x) {
        console.log('左旋：' + x.key)
        let y = x.right
        x.right = y.left
        if (y.left !== Nil) {
            y.left.parent = x
        }
        y.parent = x.parent
        if (x.parent === Nil) {
            root = y
        } else if (x === x.parent.left) {
            x.parent.left = y
        } else {
            x.parent.right = y
        }
        y.left = x
        x.parent = y
    }
    /**
     * 
     *    |-----yB-----|
     * |--xR--|
     * zR     t1   
     * @param {object} y 平衡因子>1,待旋转的节点
     */
    function rightRotate(x) {
        console.log('右旋：' + x.key)
        let y = x.left
        x.left = y.right
        if (y.right !== Nil) {
            y.right.parent = x
        }
        y.parent = x.parent
        if (x.parent === Nil) {
            root = y
        } else if (x === x.parent.right) {
            x.parent.right = y
        } else {
            x.parent.left = y
        }
        y.right = x
        x.parent = y
    }

    /**
     * 查询
     * @param {number} tree 结点的键值
     * @returns 查询结果，若查到返回
     */
    function search(key) {
        function search(node) {
            if (node) {
                if (node.key === key) {
                    return node
                } else if (key < node.key) {
                    return search(node.left)
                } else {
                    return search(node.right)
                }
            }
        }
        return search(root)
    }

    /**
     * 删除
     * @param {number} tree 结点的键值
     */
    this.delete = (key) => {
        console.log('----------------------删除节点:' + key)
        let originDeleteNode = search(key)
        if (originDeleteNode === -1) {
            console.log('note find')
            return
        }
        let deleteNode = originDeleteNode
        let originDeleteColor = deleteNode.color
        let balanceNode
        if (deleteNode.left === Nil) {
            balanceNode = deleteNode.right
            transplant(deleteNode, deleteNode.right)
        } else if (deleteNode.right === Nil) {
            balanceNode = deleteNode.left
            transplant(deleteNode, deleteNode.left)
        } else {
            deleteNode = minNode(deleteNode.right)
            originDeleteColor = deleteNode.color
            balanceNode = deleteNode.right
            if (deleteNode.parent === originDeleteNode) {
                balanceNode.parent = deleteNode
            } else {
                transplant(deleteNode, deleteNode.right)
                deleteNode.right = originDeleteNode.right
                deleteNode.right.parent = deleteNode
            }
            deleteNode.left = originDeleteNode.left
            deleteNode.left.parent = deleteNode
            if (originDeleteNode.parent === Nil) {
                root = deleteNode
            } else if (originDeleteNode === originDeleteNode.parent.left) {
                originDeleteNode.parent.left = deleteNode
            } else {
                originDeleteNode.parent.right = deleteNode
            }
            deleteNode.parent=originDeleteNode.parent
            deleteNode.color = originDeleteNode.color
        }
        treeUnit.printTree(tree.createTreeArray())
        if (!originDeleteColor) {
            //删除节点为黑色
            fixUpDelete(balanceNode)
        }
        treeUnit.printTree(tree.createTreeArray())
    }

    function fixUpDelete(balanceNode) {
        let brother
        while (balanceNode !== root && !isRed(balanceNode)) {
            if (balanceNode === balanceNode.parent.left) {
                brother = balanceNode.parent.right
                if (isRed(brother)) {
                    brother.color = false
                    balanceNode.parent.color = true
                    leftRotate(balanceNode.parent)
                    brother = balanceNode.parent.right
                }
                if (!isRed(brother.left) && !isRed(brother.right)) {
                    brother.color = true
                    balanceNode = balanceNode.parent
                    continue
                } else if (!isRed(brother.right)) {
                    brother.left.color = false
                    brother.color = true
                    rightRotate(brother)
                    brother = balanceNode.parent.right
                }
                brother.color = balanceNode.parent.color
                balanceNode.parent.color = false
                brother.right.color = false
                leftRotate(balanceNode.parent)
                balanceNode = root
            } else {
                brother = balanceNode.parent.left
                if (isRed(brother)) {
                    brother.color = false
                    balanceNode.parent.color = true
                    rightRotate(balanceNode.parent)
                    brother = balanceNode.parent.left
                }
                if (!isRed(brother.left) && !isRed(brother.right)) {
                    brother.color = true
                    balanceNode = balanceNode.parent
                    continue
                } else if (!isRed(brother.left)) {
                    brother.right.color = false
                    brother.color = true
                    leftRotate(brother)
                    brother = balanceNode.parent.left
                }
                brother.color = balanceNode.parent.color
                balanceNode.parent.color = false
                brother.left.color = false
                rightRotate(balanceNode.parent)
                balanceNode = root
            }
        }
        balanceNode.color = false
    }

    function transplant(deleteNode, deleteNodeChild) {
        if (deleteNode.parent === Nil) {
            root = deleteNodeChild
        } else if (deleteNode === deleteNode.parent.left) {
            deleteNode.parent.left = deleteNodeChild
        } else {
            deleteNode.parent.right = deleteNodeChild
        }
        deleteNodeChild.parent = deleteNode.parent
    }

    function minNode(tree) {
        if (tree.left !== Nil) {
            return minNode(tree.left)
        } else {
            return tree
        }
    }

    function maxNode(tree) {
        if (tree.right !== Nil) {
            return maxNode(tree.right)
        } else {
            return tree
        }
    }

    this.search = (key) => {
        var result = search(key)
        return result === undefined ? -1 : result.key
    }

    this.getRoot = () => {
        return root
    }
}

let tree = new TreeCode();
tree.createTree()
treeUnit.printTree(tree.createTreeArray())
// tree.delete(3)
// tree.delete(6)
// tree.delete(5)
tree.delete(9)
tree.delete(10)
// tree.delete(12)
tree.delete(11)
tree.delete(2)